package com.java.comprehensive.arithmetic.leecode.easy;

import util.QueueNode;
import util.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: comprehensive-service
 *
 * @description: 二叉树的最小深度
 *
 * @author: 窦绍飞
 *
 * @create: 2021-12-06 18:31
 **/
public class LeetCode_111 {

	public static int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		if (root.right == null && root.left == null) {
			return 1;
		}
		int i = Integer.MAX_VALUE;
		if (root.left != null) {
			i = Math.min(minDepth(root.left), i);
		}
		if (root.right != null) {
			i = Math.min(minDepth(root.right), i);
		}
		return i + 1;
	}

	public static int breadthDepth(TreeNode root) {

		if (root == null) {
			return 0;
		}
		Queue<QueueNode> queue = new LinkedList<>();
		queue.offer(new QueueNode(root, 1));
		while (!queue.isEmpty()) {
			QueueNode nodeDepth = queue.poll();
			TreeNode node = nodeDepth.node;
			int depth = nodeDepth.depth;
			if (node.left == null && node.right == null) {
				return depth;
			}
			if (node.left != null) {
				queue.offer(new QueueNode(node.left, depth + 1));
			}
			if (node.right != null) {
				queue.offer(new QueueNode(node.right, depth + 1));
			}
		}
		return 0;
	}

	public static void main(String[] args) {

		TreeNode treeNode8 = new TreeNode(15, null, null);
		TreeNode treeNode9 = new TreeNode(4, null, treeNode8);
		TreeNode treeNode3 = new TreeNode(2, null, null);
		TreeNode treeNode4 = new TreeNode(3, null, treeNode9);
		TreeNode treeNode2 = new TreeNode(9, null, null);
		TreeNode treeNode = new TreeNode(2, treeNode3, treeNode4);
		int i = breadthDepth(treeNode);
		System.out.println(i);
	}
}
